n=100;
m=100;
p=[42428,47871,23120,55960,74776,1195,78645,34475,94678,79660,80961,54350,13321,73846,76945,60446,66778,79715,17747,54055,50210,43496,97302,86797,37977,42410,52060,28803,68279,13332,57755,43966,3228,48632,17195,73981,41377,88534,25947,65255,87066,47479,47789,51714,7726,34211,51365,55123,13317,8915,26299,83133,59418,89438,10441,67214,20632,32583,91568,15210,7811,70803,38373,5732,22503,90930,92834,89388,73344,43239,82098,64854,47173,3390,72117,15323,9960,75216,497,39071,36570,97933,81014,46200,49355,76095,69268,37877,73272,30136,75014,4261,5288,69336,82214,10424,89005,41647,25710,88408];
road=[|1,2|
2,3|
3,4|
4,5|
5,6|
6,7|
7,8|
8,9|
9,10|
10,11|
11,12|
12,13|
13,14|
14,15|
15,16|
16,17|
17,18|
18,19|
19,20|
20,21|
21,22|
22,23|
23,24|
24,25|
25,26|
26,27|
27,28|
28,29|
29,30|
30,31|
31,32|
32,33|
33,34|
34,35|
35,36|
36,37|
37,38|
38,39|
39,40|
40,41|
41,42|
42,43|
43,44|
44,45|
45,46|
46,47|
47,48|
48,49|
49,50|
50,51|
51,52|
52,53|
53,54|
54,55|
55,56|
56,57|
57,58|
58,59|
59,60|
60,61|
61,62|
62,63|
63,64|
64,65|
65,66|
66,67|
67,68|
68,69|
69,70|
70,71|
71,72|
72,73|
73,74|
74,75|
75,76|
76,77|
77,78|
78,79|
79,80|
80,81|
81,82|
82,83|
83,84|
84,85|
85,86|
86,87|
87,88|
88,89|
89,90|
90,91|
91,92|
92,93|
93,94|
94,95|
95,96|
96,97|
97,98|
98,99|
99,100|];
request=[|39,0,92,1|
36,0,84,0|
100,1,6,0|
21,1,78,1|
52,0,31,1|
49,1,1,1|
74,1,6,1|
39,0,71,0|
71,1,97,1|
55,0,84,1|
66,0,47,1|
44,1,23,0|
32,0,36,1|
46,1,92,1|
8,1,33,0|
27,1,94,1|
31,1,66,1|
60,1,12,0|
20,0,94,0|
27,0,83,1|
27,0,66,1|
83,0,77,1|
79,0,48,1|
39,1,82,0|
61,0,50,0|
25,0,38,0|
94,1,74,1|
95,0,5,1|
53,0,18,1|
30,1,13,0|
68,1,26,1|
98,0,31,1|
11,1,96,0|
39,1,84,1|
46,0,99,0|
22,0,20,1|
31,1,76,1|
76,1,60,0|
33,1,75,1|
46,1,27,1|
39,0,33,1|
22,1,47,1|
91,1,12,1|
25,1,67,0|
36,1,71,0|
55,0,49,0|
22,0,13,0|
26,1,84,0|
64,0,56,1|
34,0,96,1|
78,1,18,1|
81,1,39,1|
81,0,80,0|
45,1,32,1|
39,0,37,0|
89,1,10,1|
2,0,16,1|
83,0,66,0|
5,1,52,1|
61,0,4,0|
84,0,77,0|
1,0,34,1|
76,1,22,1|
74,0,58,1|
21,1,47,1|
87,0,70,1|
6,1,60,0|
39,1,62,1|
72,1,84,0|
27,0,92,1|
57,0,51,1|
97,1,5,0|
45,0,91,1|
57,1,56,0|
79,1,81,1|
58,0,35,1|
95,1,81,1|
40,0,12,1|
71,0,41,1|
53,1,62,0|
88,0,16,1|
49,0,67,1|
33,1,98,0|
88,0,78,1|
81,0,55,0|
83,1,28,0|
74,1,62,1|
66,0,69,1|
48,1,7,1|
95,0,68,0|
68,0,41,1|
84,1,82,1|
76,0,17,1|
82,0,48,0|
96,1,19,0|
94,0,14,1|
30,1,73,0|
72,1,99,1|
66,0,12,1|
21,1,35,1|];